/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.tree

import junit.framework.TestCase.assertEquals
import org.jheaps.AddressableHeap
import org.jheaps.MergeableDoubleEndedAddressableHeap
import org.junit.Assert
import org.junit.BeforeClass
import org.junit.Test
import java.io.Serializable

abstract class AbstractMergeableDoubleEndedAddressableHeapTest {
    private class TestComparator : Comparator<Int?>, Serializable {
        override fun compare(o1: Int?, o2: Int?): Int {
            return if (o1!! < o2!!) {
                1
            } else if (o1 > o2) {
                -1
            } else {
                0
            }
        }

        companion object {
            private const val serialVersionUID = 1L
        }
    }

    protected abstract fun createHeap(): MergeableDoubleEndedAddressableHeap<Int, String>

    protected abstract fun createHeap(comparator: Comparator<Int?>?): MergeableDoubleEndedAddressableHeap<Int, String>

    @Test
    fun testMeld1() {
        val a = createHeap()
        a.insert(10)
        a.insert(11)
        a.insert(12)
        a.insert(13)

        val b = createHeap()
        b.insert(14)
        b.insert(15)
        b.insert(16)
        val b4: AddressableHeap.Handle<Int, String> = b.insert(17)

        a.meld(b)

        Assert.assertEquals(8, a.size())
        Assert.assertTrue(b.isEmpty)
        Assert.assertEquals(0, b.size())

        b4.decreaseKey(9)
        assertEquals(9, a.findMin().key)
    }

    @Test
    fun testMeld2() {
        val a = createHeap()
        a.insert(10)
        a.insert(11)
        a.insert(12)
        a.insert(13)

        val b = createHeap()
        b.insert(14)
        b.insert(15)
        b.insert(16)
        val b4: AddressableHeap.Handle<Int, String> = b.insert(17)

        val c = createHeap()
        c.insert(18)
        c.insert(19)
        c.insert(20)
        val c4: AddressableHeap.Handle<Int, String> = c.insert(21)

        a.meld(b)
        a.meld(c)

        Assert.assertEquals(12, a.size())
        Assert.assertTrue(b.isEmpty)
        Assert.assertEquals(0, b.size())

        Assert.assertTrue(c.isEmpty)
        Assert.assertEquals(0, c.size())

        assertEquals(10, a.findMin().key)
        b4.decreaseKey(9)
        assertEquals(9, a.findMin().key)
        c4.decreaseKey(8)
        assertEquals(8, a.findMin().key)
    }

    @Test(expected = IllegalStateException::class)
    fun testMultipleMelds() {
        val a = createHeap()
        a.insert(10)
        a.insert(11)
        a.insert(12)
        a.insert(13)

        val b = createHeap()
        b.insert(14)
        b.insert(15)
        b.insert(16)
        b.insert(17)

        val c = createHeap()
        c.insert(18)
        c.insert(19)
        c.insert(20)
        c.insert(21)

        a.meld(b)
        a.meld(b)
    }

    @Test(expected = IllegalStateException::class)
    fun testInsertAfterAMeld() {
        val a = createHeap()
        a.insert(10)
        a.insert(11)
        a.insert(12)
        a.insert(13)

        val b = createHeap()
        b.insert(14)
        b.insert(15)
        b.insert(16)
        b.insert(17)

        a.meld(b)
        b.insert(30)
    }

    @Test
    fun testCascadingMelds() {
        val a = createHeap()
        a.insert(10)
        a.insert(11)
        a.insert(12)
        a.insert(13)

        val b = createHeap()
        b.insert(14)
        b.insert(15)
        b.insert(16)
        b.insert(17)

        val c = createHeap()
        c.insert(18)
        c.insert(19)
        c.insert(20)
        c.insert(21)

        val d = createHeap()
        d.insert(22)
        d.insert(23)
        d.insert(24)
        d.insert(25)

        val e = createHeap()
        e.insert(26)
        e.insert(27)
        val e3: AddressableHeap.Handle<Int, String> = e.insert(28)
        val e4: AddressableHeap.Handle<Int, String> = e.insert(29)

        d.meld(e)
        c.meld(d)
        b.meld(c)
        a.meld(b)

        Assert.assertEquals(20, a.size())
        Assert.assertEquals(0, b.size())
        Assert.assertEquals(0, c.size())
        Assert.assertEquals(0, d.size())
        Assert.assertEquals(0, e.size())

        assertEquals(10, a.findMin().key)
        e4.decreaseKey(9)
        assertEquals(9, a.findMin().key)
        e3.decreaseKey(8)
        assertEquals(8, a.findMin().key)
        e3.delete()
        assertEquals(9, a.findMin().key)
    }

    @Test
    fun testMeldGeneric() {
        val h1 = createHeap()

        for (i in 0 until SIZE) {
            h1.insert(2 * i)
        }

        val h2 = createHeap()
        for (i in 0 until SIZE) {
            h2.insert(2 * i + 1)
        }

        h1.meld(h2)

        Assert.assertEquals(h1.size(), (SIZE * 2).toLong())
        Assert.assertEquals(h2.size(), 0)

        var prev: Int? = null
        var cur: Int
        while (!h1.isEmpty) {
            cur = h1.findMin().key
            h1.deleteMin()
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testMeldGeneric1() {
        val h1 = createHeap()

        val h2 = createHeap()
        for (i in 0 until SIZE) {
            h2.insert(i)
        }

        h1.meld(h2)

        Assert.assertEquals(h1.size(), SIZE.toLong())
        Assert.assertEquals(h2.size(), 0)

        var prev: Int? = null
        var cur: Int
        while (!h1.isEmpty) {
            cur = h1.findMin().key
            h1.deleteMin()
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testMeldGeneric2() {
        val h1 = createHeap()

        val h2 = createHeap()
        for (i in 0 until SIZE) {
            h1.insert(i)
        }

        h1.meld(h2)

        Assert.assertEquals(h1.size(), SIZE.toLong())
        Assert.assertEquals(h2.size(), 0)

        var prev: Int? = null
        var cur: Int
        while (!h1.isEmpty) {
            cur = h1.findMin().key
            h1.deleteMin()
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testMeld() {
        val h1 = createHeap()
        val h2 = createHeap()

        for (i in 0 until SIZE) {
            if (i % 2 == 0) {
                h1.insert(i)
            } else {
                h2.insert(i)
            }
        }

        h1.meld(h2)

        Assert.assertTrue(h2.isEmpty)
        Assert.assertEquals(0, h2.size())

        for (i in 0 until SIZE) {
            assertEquals(i, h1.findMin().key)
            h1.deleteMin()
        }
        Assert.assertTrue(h1.isEmpty)
    }

    @Test
    fun testMeldWithComparator() {
        val h1 = createHeap(comparator)
        val h2 = createHeap(comparator)

        for (i in 0 until SIZE) {
            if (i % 2 == 0) {
                h1.insert(i)
            } else {
                h2.insert(i)
            }
        }

        h1.meld(h2)

        Assert.assertTrue(h2.isEmpty)
        Assert.assertEquals(0, h2.size())

        for (i in 0 until SIZE) {
            assertEquals(SIZE - i - 1, h1.findMin().key)
            h1.deleteMin()
        }
        Assert.assertTrue(h1.isEmpty)
    }

    @Test
    fun testMeldBadComparator() {
        val h1 = createHeap(comparator)
        val h2 = createHeap(Comparator { o1, o2 -> o1!! - o2!! })

        for (i in 0 until SIZE) {
            if (i % 2 == 0) {
                h1.insert(i)
            } else {
                h2.insert(i)
            }
        }

        try {
            h1.meld(h2)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }
    }

    @Test
    fun testMeldBadComparator1() {
        val h1 = createHeap(comparator)
        val h2 = createHeap(null)
        try {
            h1.meld(h2)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }
    }

    @Test
    fun testMeldEvenOddSizes() {
        val a = createHeap()
        a.insert(10)
        a.insert(11)
        a.insert(12)
        a.insert(13)

        val b = createHeap()
        b.insert(14)
        b.insert(15)
        b.insert(16)

        a.meld(b)

        Assert.assertEquals(7, a.size())
        Assert.assertTrue(b.isEmpty)
        Assert.assertEquals(0, b.size())

        assertEquals(10, a.findMin().key)
        assertEquals(16, a.findMax()!!.key)
    }

    @Test
    fun testMeldOddOddSizes() {
        val a = createHeap()
        a.insert(10)
        a.insert(11)
        a.insert(12)

        val b = createHeap()
        b.insert(14)
        b.insert(15)
        b.insert(16)

        a.meld(b)

        Assert.assertEquals(6, a.size())
        Assert.assertTrue(b.isEmpty)
        Assert.assertEquals(0, b.size())

        assertEquals(10, a.findMin().key)
        assertEquals(16, a.findMax()!!.key)
    }

    @Test
    fun testMeldOddEvenSizes() {
        val a = createHeap()
        a.insert(10)
        a.insert(11)
        a.insert(12)

        val b = createHeap()
        b.insert(13)
        b.insert(14)
        b.insert(15)
        b.insert(16)

        a.meld(b)

        Assert.assertEquals(7, a.size())
        Assert.assertTrue(b.isEmpty)
        Assert.assertEquals(0, b.size())

        assertEquals(10, a.findMin().key)
        assertEquals(16, a.findMax()!!.key)
    }

    companion object {
        protected const val SIZE: Int = 100000

        private var comparator: Comparator<Int?>? = null

        @JvmStatic
        @BeforeClass
        fun setUpClass(): Unit {
            comparator = TestComparator()
        }
    }
}
